package Alibaba;


import common.TreeNode;

/**
 * @author zhangmin
 * @create 2022-01-31 13:33
 * 543. 二叉树的直径
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。
 * 这条路径可能穿过也可能不穿过根结点。
 */
public class diameterOfBinaryTree543 {
    int maxPath=0;
    //求root为根的子树的高度
    int deep(TreeNode root){
        if (root==null){
            return 0;
        }
        int leftdeep = deep(root.left);
        int rightdeep = deep(root.right);
        int path= leftdeep + leftdeep;
        maxPath=Math.max(maxPath,path);
        return Math.max(leftdeep, rightdeep)+1;
    }

    public int diameterOfBinaryTree(TreeNode root) {
        deep(root);
        return maxPath;
    }
}
